Many of the tasks that are addressed by decision-making systems and artificial intelligence systems can be represented as constraint satisfaction problems (“CSP”s). In this representation, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of constraints that the variables must simultaneously satisfy. The set of variables, domains and constraints is referred to as a CSP. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to a CSP is an assignment of a value to all the variables from their respective domains that satisfies all of the constraints.
A constraint based system includes a constraint solver that attempts to find one or more solutions to a given CSP, or prove that no solution exists. Constraint based systems are used for many artificial intelligence related applications and a variety of other applications, including: (1) Product configurators; (2) Robotic control; (3) Temporal reasoning; (4) Natural language processing; (5) Spatial reasoning; (6) Test-case generation for software and hardware systems; (7) Machine vision; (8) Medical diagnosis; (9) Resource allocation; and (10) Frequency allocation.
The network of constraints in a CSP can be viewed as a graph, having a node for each variable and an “arc” for each constraint. The members of each arc are the variables that appear in the constraint to which the arc corresponds. An arc is said to be consistent if for any variable of the arc, and any value in the domain of the variable, there is a valid assignment of values to the other variables on the arc that satisfies the constraint represented by the arc.
Classes of problems exist which are comprised of very large sets of variables that may only be conditionally related or required for a solution. One example of such problems is the configuration of large component-based systems. For example, selecting a type of hard disk controller for a computer configuration is not needed if a hard disk has not been chosen as a form of storage. If instead flash memory is chosen, a different set of variables and constraints would be required to be solved. Techniques have been developed to allow such large problems to be represented as a set of smaller sub-problems, conditionally related through composition or association. A “dynamic constraint satisfaction problem” is one in which these sub-problems of variables and constraints can be incrementally added as required, either explicitly or as a result of inference from the propagation of constraints.